翻訳と辞書
Words near each other
・ Lineodes aztecalis
・ Lineodes caracasia
・ Lineodes contortalis
・ Lineodes convolutalis
・ Lineodes craspediodonta
・ Lineodes dianalis
・ Lineodes elcodes
・ Lineodes encystalis
・ Lineodes fontella
・ Lineodes formosalis
・ Lineodes furcillata
・ Linear predictive analysis
・ Linear predictive coding
・ Linear predictor function
・ Linear probability model
Linear probing
・ Linear production game
・ Linear programming
・ Linear programming decoding
・ Linear programming formulation
・ Linear programming relaxation
・ Linear progression
・ Linear range
・ Linear Recording
・ Linear referencing
・ Linear regression
・ Linear regression (disambiguation)
・ Linear regulator
・ Linear response function
・ Linear scale


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

Linear probing : ウィキペディア英語版
Linear probing
Linear probing is a scheme in computer programming for resolving hash collisions of values of hash functions by sequentially searching the hash table for a free location.
==Algorithm==
Linear probing is accomplished using two values - one as a starting value and one as an interval between successive values in modular arithmetic. The second value, which is the same for all keys and known as the ''stepsize'', is repeatedly added to the starting value until a free space is found, or the entire table is traversed. (In order to traverse the entire table the stepsize should be relatively prime to the arraysize, which is why the array size is often chosen to be a prime number.)
::newLocation = (startingValue + stepSize) % arraySize
Given an ordinary hash function ''H(x)'', a linear probing function (''H(x, i)'') would be:
:: H(x, i) = (H(x) + i) \pmod n.\,
Here ''H(x)'' is the starting value, ''n'' the size of the hash table, and the ''stepsize'' is ''i'' in this case.
Often, the step size is one; that is, the array cells that are probed are consecutive in the hash table. Double hashing is a variant of the same method in which the step size is itself computed by a hash function.

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「Linear probing」の詳細全文を読む



スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.